package com.company.ljh.easy;

import com.company.ljh.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * 872. 叶子相似的树
 * 简单
 * 211
 * 相关企业
 * 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
 *
 *
 *
 * 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
 *
 * 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 *
 * 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 * @projectName:leet_code
 * @see:com.company.ljh.easy
 * @author:ljh
 * @createTime:2023/7/4 16:02
 * @version:1.0
 */
public class 叶子相似的树 {
    //按顺序保存叶子节点即可
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> leafNodeList1 = new ArrayList();
        List<Integer> leafNodeList2 = new ArrayList();
        //遍历第一个Tree，保存叶子节点
        traversalTree(root1,leafNodeList1);
        traversalTree(root2,leafNodeList2);
        if(leafNodeList1.size() == leafNodeList2.size()){
            for(int i =0;i< leafNodeList1.size();i++){
                if(leafNodeList1.get(i) != leafNodeList2.get(i)){
                    return false;
                }
            }
            return true;
        }
        return false;
    }
    //前序遍历
    public void traversalTree(TreeNode node,List<Integer> leafNodeList){
        if(node == null){
            return;
        }
        if(node.left == null && node.right == null){
            leafNodeList.add(node.val);
        }
        traversalTree(node.left,leafNodeList);
        traversalTree(node.right,leafNodeList);
    }
}
